package sort

/*
二分查找
 */

func binarySearch(list []int, val int) (bool, int) {
	//奇数
	//odd := len(list) % 2 == 1
	start := 0
	end := len(list)
	var pos int
	for {
		tmp := list[start:end]
		if isOdd(tmp) {
			pos = len(tmp) / 2 + 1
			if pos == 1 {
				if tmp[0] == val {
					return true, pos
				} else {
					break
				}
			}
		} else {
			pos = len(tmp) / 2
		}

		if tmp[pos - 1] > val {
			end = pos - 1
		} else if tmp[pos - 1] < val {
			start = pos
		} else {
			return true, pos - 1
		}
	}

	return false, -1
}

// 判断奇数
func isOdd(list []int) bool {
	return len(list) % 2 == 1
}

func binarySearchV2(list []int, target int) bool {
	if len(list) == 1 {
		if list[0] == target {
			return true
		} else {
			return false
		}
	}
	var pos int
	if isOdd(list) {
		pos = len(list) / 2 + 1
	} else {
		pos = len(list) / 2
	}

	start := 0
	end := len(list)

	if target < list[pos - 1] {
		end = pos - 1
		return binarySearchV2(list[start:end], target)
	} else if target > list[pos - 1] {
		start = pos
		return binarySearchV2(list[start:end], target)
	} else {
		return true
	}
}

